#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1944. 队列中可以看到的人数
// 【难度】困难
// 【提交】2025.9.15 https://leetcode.cn/problems/number-of-visible-people-in-a-queue/submissions/663009567/
// 【标签】单调栈；逆向遍历
class Solution_LC1944 {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n, 0);
        stack<int> stk;

        for (int i = n - 1; i >= 0; i--) {
            int x = heights[i];
            while (!stk.empty() && x > stk.top()) {
                stk.pop();
                ans[i]++;
            }
            if (!stk.empty()) {
                ans[i]++;
            }
            stk.push(x);
        }
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个数组 heights，表示队列中每个人的身高。返回一个数组 ans，其中 ans[i] 是第 i 个人向右能看到的人数。
 * 规则：第 i 个人能看到第 j 个人（j>i）的条件是两者之间的所有人都比两人矮。即，第 i 个人向右看时，第一个比他自己高的人会挡住后面所有人。
 * 模型：单调栈（Monotonic Stack），用于高效找到下一个更大元素。
 * 
 * 二、标准解法状态设计
 * 从右向左遍历，维护一个单调递减栈（栈底最大，栈顶最小）。对于当前人 i：
 *   - 弹出所有比 i 矮的人（这些矮的人会被 i 挡住，且 i 能看到他们）；
 *   - 若栈非空，说明还有一个比 i 高的人（i 能看到他）；
 *   - 将 i 入栈。
 * 
 * 三、你的实现思路
 * 使用逆向遍历和单调栈，准确处理了“可见”条件的逻辑，代码简洁高效。
 * 
 * 四、逐行注释（带细节提醒）
 * vector<int> ans(n, 0);        // 初始化答案数组，默认不可见任何人
 * stack<int> stk;               // 单调栈（递减）
 * for (int i = n - 1; i >= 0; i--) {  // 逆向遍历确保能处理右侧关系
 *     int x = heights[i];
 *     while (!stk.empty() && x > stk.top()) {  // 弹出所有比当前矮的人
 *         stk.pop();
 *         ans[i]++;              // 当前人能看见这个矮的人
 *     }
 *     if (!stk.empty()) ans[i]++; // 当前人还能看见一个更高的人（若存在）
 *     stk.push(x);               // 当前人入栈，保持栈单调递减
 * }
 * 
 * 五、正确性证明
 * 单调栈维护了右侧“可能被看见”的人（身高递减）。当前人 i 会弹出所有比他矮的人（这些矮的人不会挡住后续视线），并记录可见人数。
 * 最后栈顶的人（若存在）是第一个比 i 高的人，i 能看到他。算法保证了每个元素入栈出栈一次，正确性由单调栈性质保证。
 * 
 * 六、复杂度
 * 时间：O(n)，每个元素最多入栈出栈一次。
 * 空间：O(n)，最坏情况下栈存储所有元素。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 思路清晰，利用单调栈高效解决问题；
 *   - 代码简洁，常数小；
 *   - 逆向遍历避免重复计算。
 * 缺点：
 *   - 栈操作可能对初学者不易理解；
 *   - 未处理输入为空的情况（但题目保证 n>=1）。
 * 
 * 八、改进建议
 * 1. 可添加提前判断：if (n == 0) return {};
 * 2. 使用更明确的变量名（如 currentHeight 代替 x）；
 * 3. 对于教学场景，可添加注释说明单调栈的维护过程。
 * 
 * 九、一句话总结
 * 单调栈逆向遍历是解决“下一个更大元素”类问题的经典方法，你的实现准确且高效，可稍作变量名优化以提升可读性。
 */